There are various methods as a method of providing a service associated with data on a position where a user is present.
For example, there is the “i-area” that is a location dependent service that can be used with “i-mode” handsets of NTT DoCoMo, Inc.
In this “i-area”, it is possible to receive data for each of areas obtained by dividing the whole country of Japan into several hundred sections according to present location data of cellular phones from a base station.
Since it is possible to provide data for each of the areas divided, there are services specialized for the areas, such as weather forecasts, maps, traffic data, and restaurants and shopping data.
As similar services, there are the GPS position data service “eznavigation” of au, the map data service “J-Navi” of J-phone, the “imadoko service” and the “mopera position data service” for PHS of NTT DoCoMo, Inc., the “position data service” of DDI pocket, the “P-navi” of TTNet, and the like.
These services can provide data common to areas in a wide range, for example, weather forecasts, maps, and traffic data of the areas.
However, these services provide, based on data of a base station of cellular phones, data according to position data indicating to which area the base station belongs.
This position data is not data indicating detailed points such as latitude and longitude but is only an area code defined by communication carriers. Since position data corresponding to a position of the base station is used, the position data may be different from a location of use by a user.
Moreover, since only areas defined in advance are used, it is impossible to provide service data specialized for areas in a narrower range.
For mobile users owning portable terminals, a system for allowing the users to access data with limited positions, times, and amounts has been developed (http://www.spacetag.jp/).
However, in this system, since a circle defined by a center coordinate (latitude and longitude) and an effective radius is used as an effective space of data, there is a problem in that it is difficult to provide data and services for areas of more complicated shapes.
Further, since data is managed using only space-time data (with a space-time as an index), there is still a problem in that it is impossible to explicitly link data to a specific object in an actual space.
Moreover, it is examined to provide diligent services and data associated with the services based on accurate position data obtained by using not only GPSs and cellular phones but also various radio communication devices.
For example, in the method disclosed in U.S. Pat. No. 6,212,392, position data corresponding to a cell is used in a radio communication system that uses cellular phones.
This method is a method of judging whether a radio communication device is located within a designated area. With this method, a service provider can define and manage an area using an area representation based on quadtree data.
However, in the method, since overlapping of areas is not allowed because of limitation of a data structure, there is a disadvantage that it is impossible to allocate a plurality of different services to an identical point (region).
The following references disclose various known apparatuses or methods:
U.S. Pat. No. 6,212,392
http://www.spacetag.jp/;
H. Samet. The Quadtree and Related Hierarchical Data Structures. ACM Computing Surveys, Vol. 16, No. 2, 1984;
N. Beckmann, H.-P. Kriegel, R. Schneider and B. Seeger. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. Proceedings of ACM SIGMOD, pp. 322-331, 1990;
V. Gaede and O. Gunther. Multidimensional Access Methods. ACM Computing Surveys, Vol. 30, No. 2, June 1998; and
A Guttman. R-Trees: a dynamic index structure for spatial searching. Proceedings of the 13th ACM SIGMOD Conference, pp. 47-57, 1984.
The following problems are inherent in the conventional techniques as described above. The problems are summarized as follows.
(1) When pieces of area data provided by a plurality of different service providers are uniformly managed, a plurality of different services may be allocated to an identical region. An identical service provider may demand to define a plurality of services. In the quadtree data used as a conventional area (space data) managing method, there is a problem in that it is impossible to define a plurality of different service provision to an identical point and it is impossible to handle a plurality of pieces of service data present in an identical area.
(2) In the quadtree data, since it is necessary to designate the number of representation levels in advance, all object areas are represented at identical resolution, i.e., identical approximation accuracy. Regardless of the fact that, depending on a type of a service, it may be unnecessary to approximate the area with a high degree of accuracy, there is a problem in that it is impossible to set a different representation level for each service area when area data is managed using the quadtree.
In realization of service and data provision depending on a predetermined position,
(1) management such as setting, update, and change of a service provision range (area), and
(2) association of positions of mobile users (portable terminals) and areas
are important and indispensable techniques.
There is a need for a method of establishing an area (or may be an n-dimensional space) representation that uses a data structure based on “R*-tree”, which is one of multi-dimensional indexes, in order to flexibly and easily manage the service provision area.
There is a need for a method of finding at high speed, from position data obtained from a terminal such as a GPS or a cellular phone carried by a mobile user, in which service provision area defined in advance the user is present, and obtaining an identifier for uniquely identifying the area using a quadtree data structure or the like for respective area representations.
Moreover, there is further a need for a method of selectively finding, based on an area identifier obtained, data concerning various services and objects associated with an area with reference to profile data of a user or data on a service provider, a spatial positional relation with adjacent areas, and the like, and presenting the data to the user.
In an embodiment, an apparatus for managing area data, comprises:
a first storage for area data;
a second storage for area data;
a storage for data associated with an area; and
a storage for region data, wherein:
the first storage for area data stores one or more first data structures for area management;
the first data structure for area management includes:                a first index data structure including a first root node corresponding to a first set of areas containing a first area, first non-leaf nodes, and first leaf nodes; and        a first data storage corresponding to the first leaf nodes;        
the second storage for area data stores one or more second data structures for area management constructed on the basis of area data collected from data in the first storage for area data based on one or more area attributes designated by a user;
the second data structure for area management includes:                a second index data structure including a second root node corresponding to a second set of areas containing second areas collected based on the one or more area attributes designated, second non-leaf nodes, and second leaf nodes; and        a second data storage corresponding to the second leaf nodes;        
the storage for data associated with an area stores data associated with an area corresponding to the first areas and the second areas;
the storage for region data stores a data structure for region management that is constructed on the basis of a node associated with a region which contains at least one or more of the first sets of areas; and
the data structure for region management includes a data structure in which at least one node for identifying the region links to either the first root node or the second root node.
In a further embodiment, a program for managing a first storage for area data, a second storage for area data, a storage for data associated with an area, and a storage for region data, which is executed in an apparatus for managing area data having a structure in which:
the first storage for area data stores one or more first data structures for area management;
the first data structure for area management includes:                a first index data structure including a first root node corresponding to a first set of areas containing a first area, first non-leaf nodes, and first leaf nodes; and        a first data storage corresponding to the first leaf nodes;        
the second storage for area data stores one or more second data structures for area management constructed on the basis of area data collected from data in the first storage for area data based on one or more area attributes designated by a user;
the second data structure for area management includes:                a second index data structure including a second root node corresponding to a second set of areas containing second areas collected based on the one or more area attributes designated, second non-leaf nodes, and second leaf nodes; and        a second data storage corresponding to the second leaf nodes;        the storage for data associated with an area stores data associated with an area corresponding to the first areas and the second areas;        
the storage for region data stores a data structure for region management that is constructed on the basis of a node associated with a region which contains at least one or more of the first sets of areas; and
the data structure for region management includes a data structure in which at least one node for identifying the region links to either the first root node or the second root node.